The present invention relates generally to the determination of coefficients of a function. More particularly, the apparatus, methods, and computer program products of the present invention relate to determining the coefficients of a function representative of an input signal as each sample of the signal is received to decrease latency in the determination of the coefficients.
Signal processing is an important function of many electronic systems. In particular, in many electronic systems, data is transmitted in signal form. Further, some electronic systems analyze and monitor the operation of mechanical or chemical systems by observing the characteristics of signals, such as vibration signals and other types of signals, that are output from these systems. In light of this, methods have been developed to characterize signals such that information or data in the signal is available for data processing.
As one example, in many electronic systems, time domain signals are typically transformed to the frequency domain prior to signal processing. A typical method for converting signals to the frequency domain is performed using Fourier Transforms. The Fourier Transform of a signal is based on a plurality of samples of the time domain signal taken over a selected time period, known as the base frequency. Based on these samples of the signal the Fourier Transform provides a plurality of coefficients, where the coefficients respectively represent the amplitude of a frequency that is a multiple of the base frequency. These coefficients of the Fourier Transform, which represent the signal in the frequency domain, are then used by electronic systems in processing the signal.
Although Fourier Transforms are among some of the most widely used functions for processing signals, there are other functions that are either currently used or will be used in the future, as a better understanding of their applicability is recognized. These functions include Bessel functions, Legendre Polynomials, Tschebysheff Polynomials of First and Second Kind, Jacoby Polynomials, Generalized Laguerre Polynomials, Hermite Polynomials, Bernoulli Polynomials, Euler Polynomials, and a variety of Matrices used in Quantum Mechanics, Linear Analysis functions, wavelets and fractals just to name a few.
Although Fourier transforms and the other functions mentioned above are useful in determining characteristics of signals for use in data processing, there are some drawbacks to their use. Specifically, application of these functions to signals is typically computationally intensive. This is disadvantageous as it may require the use of specialized processors in order to perform data processing. Further, and even more importantly, the time required to perform the number of computations using these functions may cause an unacceptable delay for many data processing applications. In fact, a goal of many data processing systems is the ability to process data signals in real time, with no delay.
For example, the Fourier Series is defined as an infinite series of coefficients representing a signal. To transform a signal using a Fourier Series would require an infinite number of computations. To remedy this problem, many conventional data processing systems use Discrete Fourier Transforms (DFT), as opposed to the infinite Fourier Series. The DFT is the digital approximation to the Fourier Series and is used to process digitized analog information. Importantly, the DFT replaces the infinite series of the Fourier Series with a finite set of N evenly spaced samples taken over a finite period. The computation of the DFT therefore provides the same number of coefficients as the samples received, instead of an infinite number of samples required by the Fourier Series. As such, use of the DFT provides the most satisfactory current means to process the signal.
Because of the importance of reducing the time required to process signals, however, methods have been developed to further reduce the number of computations required to perform a DFT of a signal. Specifically, the DFT procedure computes each coefficient by a similar process. The process for a general coefficient is; multiply each sample by the sine or cosine of the normalized value of the independent variable times the angular rate and sum over all of the samples. This procedure defines N multiply-add steps for each of N coefficients, which in turn, equates to N2 multiply-add computations per DFT. As many samples of a signal are typically required to perform an adequate approximation of the signal, the DFT of a signal is typically computational and time intensive.
One of the methods developed to reduce the number of computations is the butterfly method, which reduces the number of computations from N2 to N times log (N). The butterfly method is based on the fact that many of the trigonometric values of the DFT are the same due to periodicity of the functions. As such, the butterfly method reduces the matrix associated with the DFT into N/2 two-point transforms (i.e., the transforms representing each coefficient an and bn). The butterfly method further reduces the redundant trigonometric values of the DFT. Although the butterfly method reduces the number of computations over the more traditional DFT method, it also adds complexity to the Fourier transformation of a signal. Specifically, the butterfly method uses a complex method for addressing the samples of the signal and the matrix containing the functions. This complexity can require the use of specialized processors and increase time for computation of the Fourier Transform. By its nature, the butterfly is a batch process, which does not begin determination of the coefficients until after all of the samples have been received. As described later, this method causes latency in the determination of the coefficients of the function.
An additional problem with the DFT, besides the number of computations required, is that the value of each coefficient of the DFT is a function of all the samples of the signal. Therefore, none of the coefficients of the DFT can be determined until all of the samples have been processed. Once the last sample of a set is received, the values of all of the coefficients can then be defined. As such, the time between the arrival of the last sample and the availability of the coefficients is referred to as the latency of the system. If the time for processing the coefficients is greater than the time to collect the set of samples, the system cannot operate in real time.
Although no coefficient is defined until all of the samples have been received, there is an advantageous property of the DFT that has not been heretofore recognized in the prior art. This property is the independence of samples. In a set of samples being transformed in a DFT process, each sample makes a contribution to each coefficient based only on the sine or cosine of the applicable angle. This is illustrated in Appendix 1. Specifically, each of the coefficients of the DFT, (i.e., A0, A1, A2, . . . and B0, B1, B2, . . . ), is the summation of the application of each sample to the sine and cosine functions associated with each coefficient. For example, the coefficient A1 is the summation A11+A12 +. . . A18, which are the application of each sample to the cosine function associated with the A1 coefficient. As each of the samples are related to each coefficient by addition, each sample is independent of the other samples and can be used to update the coefficients prior to receipt of the other samples.
Many conventional systems for determining the Fourier Transform of a signal do not recognize this independence of samples aspect of the DFT. Specifically, conventional systems that use the DFT typically first receive a number of samples N of a signal, and only after all of the samples have been received does the system generate each of the coefficients. As such, these conventional systems have an associated latency equal to the time required for the system to compute each of the coefficients after the last sample is received. This latency may be significant. For example, if a conventional system determines a DFT using N=64 samples, then the number of computations is N2 or 4096. For the Fast Fourier Transform (FFT), this is reduced to N times log (N) or 64(6) equals 364.
Appendix 1 illustrates an example of a data processing system that waits until all of the samples have been received prior to determining the coefficients of the DFT. As can be seen, the data processing system illustrated in Appendix 1, first receives eight samples of the signal prior to beginning to process any of the coefficients of the Fourier Transform. Only after receipt of the samples does the system begin to calculate the coefficients. As latency is defined as the time between the receipt of the last sample and the time at which the coefficients are available, this data processing system has latency equal to the time required to perform all computations of the coefficients. As such, this data processing system cannot be used for real-time data processing. As real-time data processing or approximate real-time data processing is advantageous for use in many data processing systems, it would be desirous to provide apparatus and methods that decrease the time required to perform transformation of signals.
An additional problem with many conventional data processing systems, such as the butterfly, is that the coefficients of the function cannot be independently observed due to the complexity of the system. Further, because the butterfly determines the coefficients in a batch method, as opposed to real time, individual coefficients can not be observed and tracked as each new sample is received. Because, the batch method of analysis adds latency, considerable processing must be employed with conventional systems to observe and track coefficients over time. Observance and tracking individual coefficients of a signal is advantageous for in-depth signal analysis.
A still further problem with many conventional data processing systems is that these systems typically do allow for variation of the resolution of individual coefficients of the function. For example, the butterfly is configured to calculate each coefficient producing the same number coefficients as of samples. This may be disadvantageous in applications in which there is interest in only one or a subset of the coefficients, as the butterfly will spend time and resources determining coefficients of less importance to the same resolution as those coefficients of importance. In light of this, it would be desirous to provide apparatus and methods that allow for the tracking and observance of individual coefficients and also varying the resolution with which individual coefficients are calculated.
As set forth below, the apparatus, methods, and computer program products of the present invention overcome many of the deficiencies identified with processing signals using functions, such as Fourier Transforms. In particular, the present invention provides apparatus, methods, and computer program products that determine the coefficients of a function representative of an input signal with reduced latency, such that the coefficients of the function are made available within a decreased time from receipt of the last sample of the signal. The present invention also provides apparatus, methods, and computer program products that reduce the amount of data that must stored in order to determine the coefficients of a function, such that less complex hardware designs can be implemented. Further, the present invention provides apparatus, methods, and computer program products that allow individual coefficients to be tracked and observed and also allows individual coefficients or subsets of coefficients to be determined with differing levels of resolution.
Specifically, in one embodiment, the present invention provides apparatus, methods, and computer program products that update at least one of the coefficients of a function prior to receipt of the last sample of the signal, such that the coefficients of the function may be determined with reduced latency. Further, in another embodiment, the apparatus, methods, and computer program products of the present invention update each of the coefficients of a function as each of the samples of the signal are received. As discussed previously, each of the samples of the signal affects the coefficients of the function independently of the other samples. The independent nature of the samples permits the equations for each coefficient to be rearranged so as to group all of the contributions from each sample separately. The result is that the contributions of each sample can be computed when the sample is received and then added to each coefficient.
In light of this, in one embodiment, the present invention includes an apparatus for determining the coefficients of a function representative of an input signal based on a predetermined plurality of samples of the input signal. The apparatus of the present invention includes a coefficient generator that receives each of the samples one at a time and updates at least one of the coefficients of the function prior to receipt of the last sample.
In another embodiment, the apparatus of the present invention includes a coefficient generator that receives each of the samples one at a time and updates the coefficients of the function based on each sample as the sample is received without awaiting receipt of all samples. The coefficients are thus updated each time before the arrival of the next sample. As such, when the last sample is received, the only remaining computations are the determination of the contribution of the last sample to each coefficient. Therefore, the latency from receipt of the last sample until the coefficients are available is reduced.
In a further embodiment of the present invention, the coefficient generator simultaneously updates each of the coefficients with a sample as it is received. As such, when the final sample is received, the coefficient generator simultaneously updates each of the coefficients and the latency between receipt of last sample and the availability of the coefficients is significantly reduced.
In addition to decreasing the latency between receipt of the last sample and availability of the coefficients, the apparatus, methods, and computer program products of the present invention also reduce hardware needed for implementation. Specifically, as discussed the apparatus, methods, and computer program products of the present invention update each of the coefficients with the contribution of each sample as the sample is received. As such, retaining the sample after each of the coefficients has been updated is not required, thereby reducing the amount of storage.
Further, the apparatus, methods, and computer program products of the present invention also decrease the time for performing computations by precalculating at least a portion of the functions associated with each coefficient and storing these pre-calculated values in memory for use in determining the coefficients for a given signal. Specifically, as discussed above and illustrated in Appendix 1, each of the samples is related to each of the coefficients by a trigonometric function, where the value of the trigonometric function is based on the coefficient and the order that the sample was received in the plurality of samples. As the coefficient and the order in which the sample is received are known before hand, the apparatus, methods, and computer program products of the present invention pre-calculate this portion of the trigonometric function for each sample and coefficient. As such, when each sample is received, the coefficient generator of the present invention need only multiply the sample by the pre-calculated value associated with the sample and coefficient.
Specifically, in one embodiment, the present invention includes an apparatus having a coefficient generator that includes a memory device. Stored in the memory device are pre-calculated values representing the mathematical function associated with each sample and coefficient. In this embodiment of the present invention, when a sample is received, the coefficient generator accesses the memory device and multiplies the sample by the value representing the mathematical function associated with the sample and coefficient to thereby define a term of the coefficient. The coefficient generator further updates the coefficient by adding the term to the previous value of the coefficient.
In an additional embodiment, the apparatus, methods, and computer program products may store each of the pre-calculated values in a memory device that includes an array having a plurality of cells, where each cell of the array stores a value representing the mathematical function associated with a respective sample and coefficient. Further, in this embodiment, each cell of the array has a unique address, which is designated by the respective coefficient and sample. As such, for each sample and coefficient, the coefficient generator of this embodiment of the present invention accesses the cell of the memory device using the address associated with the sample and coefficient, multiplies the sample by the stored value to thereby define a term of the coefficient, and thereafter updates the coefficient by adding the term to the previous value of the coefficient.
In addition to reducing the required number of calculations by precalculating the function associated with each sample and coefficient, in one embodiment, the apparatus, method, and computer program product of the present invention also pre-calculates all the possible values of the magnitude of the sample with the trigonometric function associated with each coefficient and sample. As such, when a sample is received, the coefficient generator need only evaluate the value of the sample and retrieve the pre-calculated value associated with the value of the sample and the mathematical function for the sample and coefficient from the memory device and use the pre-calculated value to update the coefficient.
For example, in one embodiment, the present invention includes an apparatus having a coefficient generator with first and second memory devices. The first memory device includes an array of cells with each cell associated with a respective sample and coefficient. Each cell contains a pre-calculated value corresponding to the combination of one of the finite number of possible values of the sample and the mathematical function associated with the respective coefficient and sample. The second memory device also has an array of cells for storing tokens. Each of the tokens represents a respective coefficient and sample.
In operation, when a sample is received, the coefficient generator accesses the second memory device and for each coefficient retrieves the token associated with the coefficient and the sample and supplies the token to the first memory device. Further, the coefficient generator receives the value of the sample and based on the token from the second memory device and the value of the sample, retrieves the pre-calculated value stored in the cell of the first memory device that has an address comprised of the token and the value of the sample. The coefficient generator further updates the coefficient by adding the pre-calculated value from the first memory device to the previous value of the coefficient.
In another embodiment, the coefficient generator includes a multiplier, adder, divider, or other gated functions, rather than a second storage device. In this embodiment, the tokens are provided by the gate to the first memory device for addressing the cells of the first memory device. In still another embodiment, a counter is decoded with or without the use of gates into tokens for addressing the second memory device, which may be conversion into values that feed a multiplier, adder, divider or other gated function, rather than a memory device.
In addition to reducing the time for calculating the coefficient based on each sample by storing pre-calculated values, the present invention also provides apparatus, methods, and computer program products that minimizes the number of values that must be stored in the memory device and the size of the token needed to address the first memory device. Specifically, due to the trigonometric nature of some functions, some of the coefficients for some samples will have a mathematical value of zero. As the trigonometric function is dependent on the coefficient and sample number, these instances can be predetermined. Further, because the value for these instance is zero, there is no need to provide storage for these values in the first memory device, thereby reducing the size of the array of the memory device and the size of the token needed to address the first storage device.
Specifically, in this embodiment of the present invention, the token also indicates if the value of the mathematical function associated with the respective sample and coefficient is zero. When a sample is received for which the trigonometric function for the sample and a coefficient is zero, the token associated with the sample and coefficient will so indicate. As such, when the coefficient generator accesses the token associated with the sample and coefficient, the coefficient generator will observe the token and update the coefficient by adding a zero to the previous value of the coefficient.
In some embodiments, the coefficient generator further includes a null device, such as a pull down circuit. In this embodiment, if the token indicates that the mathematical function is zero, the null device replaces the output of the first memory device with a zero value for addition to the coefficient.
To further minimize storage, in one embodiment, the present invention provides apparatus, methods, and computer program products that stores only pre-calculated values corresponding to the combination of a respective sample and the magnitude of a respective mathematical function, without accounting for the sign of the mathematical function. Specifically, due to the periodic nature of some functions, some of the mathematical functions associated with the respective sample and coefficients have the same magnitude, but different signs. In this embodiment, of the present invention, only the magnitude of each value is stored in the memory device. Further, the sign of the value is indicated in the token. As such, less storage is needed for the values.
In one embodiment of the present invention, the coefficient generator further includes an adder in electrical connection with the output of the first memory device. If the token indicates that the mathematical function is negative, the adder using twos-complement takes the negative of the magnitude of the mathematical function output by the first memory device.
As detailed above, the present invention determines the coefficients of the function representative of signal by combining each sample upon receipt with the mathematical function associated with the sample and the coefficient. Further, as detailed above, the different combinations of the samples and coefficients are pre-calculated and stored in an addressable memory device. Typically, the tokens that address the cells of the memory device have bits indicating the coefficient and bits indicating the sample. While in the normal operation, the tokens and memory device are used to determine the coefficients of a function that is representative of a signal; these tokens and memory device may also be used to determine the coefficients of an inverse function of a signal. Specifically, in one embodiment, the coefficient generator further includes a selector in electrical connection with either the gate, counter, second memory device used to generate the tokens for addressing the first memory device. If the coefficients for an inverse function of a signal are desired, the selector alters the address indicated by the token such that the token addresses a cell of the first memory device containing a pre-calculated value representing an inverse mathematical function of the signal.
As detailed above, the present invention determines the coefficients of the function representative of signal by combining each sample upon receipt with the mathematical function associated with the sample and the coefficient. Further, as detailed above, the different combinations of the samples and coefficients may be pre-calculated and stored in an addressable memory device or may be computed by a gated function with reference to a value associated with the token. Typically, the tokens that address the cells of the memory device are derived from state information obtained from the counter indicating the coefficient and the sample. While in the normal operation, the tokens and memory device are used to determine the coefficients of a function that is representative of a signal, these tokens and memory devices may also be used repetitively by adding bits to the counter at appropriate locations and thus service a multiplicity of channels. In this embodiment, additional coefficient memory cells maintain the additional coefficients, and a channel number may be output as a convenience to the user. It is still possible employ an electrical signal to determine the forward coefficients or to determine the inverse function of the input.
Further, while in the normal operation, the tokens and memory device are used to determine the coefficients of a function that is representative of a signal, these tokens and memory devices may also be used repetitively by adding bits to the counter at appropriate locations and thus service a multiplicity of channels. In this embodiment, additional coefficient memory cells maintain the additional coefficients, and a channel number may be output as a convenience to the user. By letting consecutive samples be treated as different channels it is possible to thus produce interleaved transforms. The interleaved transforms may be sent to a second similar process to produce two-dimensional transforms, as one example.
In a further embodiment, the coefficient generator receives samples from a plurality of different signals on different channels. In this embodiment, the coefficient generator, via the selector, may provide the coefficients of a function representative of one signal, while also providing the coefficients of an inverse function of another signal.
As detailed above, the apparatus, methods, and computer program products of the present invention process a plurality of samples and generate the coefficients of the function based on the samples. In some embodiments of the present invention, after the plurality of samples have been received, the apparatus, methods, and computer program products of the present invention output the generated coefficients, reset the coefficients, and again take samples of the signal. In some embodiments, however, it may be advantageous to generate and output a complete set of coefficients as each new sample is received and processed. This is referred to as a Sliding Aperture Fourier Transform (SAFT).
In this embodiment, the apparatus, methods, and computer program products of the present invention do not reset each of the coefficients to zero after the final sample of a plurality of samples has been received and the coefficients have been output. Instead, the apparatus, methods, and computer program products of the present invention replace the first sample of the previous plurality of samples with the next received sample. Using this new sample, the apparatus, methods, and computer program products of the present invention output a next set of coefficients. As such, instead of generating a set of coefficients for each xe2x80x9cbatchxe2x80x9d of samples, the apparatus, methods, and computer program products of the present invention generates a set of coefficients each time a new sample is received, thereby providing new set of coefficients for each time a new sample is received.
The present invention provides several apparatus, methods, and computer program products for generating a set of coefficients each time a new sample is received. In each of these embodiments, the apparatus, methods, and computer program products of the present invention replace the first sample of the previous plurality of samples with the next sample received and then outputs the new coefficients. For example, in one embodiment, the apparatus, methods, and computer program products of the present invention initially store each of the samples as they are received and generates a first set of coefficients when the last sample of the plurality of samples has been received. Further, when a new sample of the input signal is received, after the predetermined plurality of samples has already been received, the apparatus, methods, and computer program products of the present invention apply the mathematical function associated with the coefficients to the sample and generate a term based on the new sample for each coefficient. To replace the new sample with the first sample of the plurality of the samples, the generated term of the new sample is subtracted from the term associated with the first sample of the predetermined plurality of samples that was previously stored in the memory device. Following this subtraction, the coefficients are updated by the difference between the terms based upon the new sample and the first sample of the predetermined plurality of samples.
In another embodiment of the present invention, to replace the new sample with the first sample of the plurality of samples, the apparatus, method, and computer program products of the present invention subtract the term based upon a first sample of the predetermined plurality of samples from each of the coefficients and adds the term based upon the new sample to each of the coefficients.
In addition to outputting coefficients for each new sample received, the apparatus, methods, and computer program products of the present invention also allow individual of subsets of coefficients to be observed and tracked over time. Specifically, as stated above, the coefficient generator of one embodiment outputs coefficients for each new sample. This provides a user with a new set of coefficients in real or near real-time for observance.
Further, as discussed, the apparatus, methods, and computer program products of the present invention update each of the coefficients of the function as each sample is received. As the coefficients are individually updated, they are more readily individually available for observance. Further, because each coefficient is updated individually, the number of updates made to each individual coefficient may be varied. As such, in one embodiment, the apparatus, methods, and computer program products of the present invention can vary the resolution to which either one or a subset of coefficients are determined by varying the number of samples by which they are updated relative to the other coefficients.
In addition, the present invention also provides methods and computer program products for reducing the number of values that must be stored to represent the possible mathematical terms of a function. Specifically, as illustrated above, time for performing computations can be conserved by precalculating and storing either portions of or all values associated with a system. However, it is often desirable to reduce the amount values that require storage to a minimum, such that standard memory devices may be used.
In one embodiment, the present invention provides methods and computer program products that initially generate a first list of all possible mathematical terms of the function. For each mathematical term, the method and computer program product systematically compare each mathematical term in the list to all other mathematical terms in the list to determine which of the mathematical terms are redundant. Further, the unique mathematical terms of the function are stored in a second list all of the unique mathematical terms of the function, such that there are no redundant mathematical terms of the function in the second list.
In one embodiment of the present invention, the function is at least periodic or reversing such that some of the mathematical terms of the function have the same magnitude and different signs. In this embodiment, the method and computer program product of the present invention compare the magnitude of each mathematical term in the list to the magnitude of each of the other mathematical terms in the list to determine which of the mathematical terms have the same magnitude. Further, the mathematical terms having unique magnitudes are stored in the second list. The method and computer program product of the present invention further includes creating a token associated with each mathematical term, where the token indicates the magnitude stored in the second list associated with the mathematical term and the sign associated with the mathematical term.
In another embodiment of the present invention, at least one of the mathematical terms has a magnitude of zero. In this embodiment, the method and computer program product create a token associated with the mathematical term indicating that the mathematical term is zero such that the mathematical term is not stored in the second list.
In another embodiment, the function is representative of a signal and is defined by samples of the signal, where a sample of the signal is one of a finite number of possible values. In this embodiment, the method and computer program product generate the first list of all possible combinations of the possible values of the sample and the mathematical terms of the function. Further, each combination in the list is systematically compared to all other combinations in the list to determine which of the combinations are redundant. Based on this comparison, all of the unique combinations are stored in the second list, such that there are no redundant combinations in the second list.